package com.samxcode.leetcode;

/**
 * Divide two integers without using multiplication, division and mod operator.
 * 
 * If it is overflow, return MAX_INT.
 * 
 * @author Sam
 *
 */
public class DivideTwoInteger {
    
    public static void main(String[] args) {
        System.out.println(divide(-1010369383, -2147483648));
    }

    public static int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        //convert the integer to long type for eliminate the strange performance of the Integer.MIN_VALUE
        long dd = Math.abs((long) dividend);
        long dr = Math.abs((long) divisor);
        int n, res = 0;
        while (dd >= dr) {
            n = 0;
            //shift divisor
            while (dd >= dr << ++n);
            res += 1 << (n - 1);
            dd -= dr << (n - 1);
        }
        return (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) ? -res : res;
    }
}
